//给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：[3,2,3]
//输出：[3] 
//
// 示例 2： 
//
// 
//输入：nums = [1]
//输出：[1]
// 
//
// 示例 3： 
//
// 
//输入：[1,1,1,3,3,2,2,2]
//输出：[1,2] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 5 * 104 
// -109 <= nums[i] <= 109 
// 
//
// 
//
// 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。 
// Related Topics 数组 哈希表 计数 排序 
// 👍 417 👎 0
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace  std;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        unordered_map<int,int> map;
        vector<int> res;
        int min = INT_MAX,max = INT_MIN;
        for(int num : nums){
            map[num]++;
            if(num > max){
                max = num;
            }else if(num < min){
                min = num;
            }

        }
        int len = nums.size();
        for (auto & pair : map) {
            if (pair.second > len / 3) {
                res.push_back(pair.first);
            }
        }
        return res;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
